/*************************************************************************
> File Name: merge_sort.c
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2023-07-20 10:23:55
> Description: 归并排序时间复杂度nlgn
************************************************************************/

#include <stdio.h>
#include "general.h"
void merge(int arr[], int start, int mid, int end);
void mergeSort(int arr[], int start, int end);

int main(int argc, char const *argv[])
{
    int arr[] = {9, 4, 2, 7, 5, 1, 8, 3, 6, 0};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArr(arr, sizeof(arr) / sizeof(int));
    mergeSort(arr, 0, size - 1);
    printf("Sorted array: \n");
    printArr(arr, sizeof(arr) / sizeof(int));
    return 0;
}
void merge(int arr[], int start, int mid, int end)
{
    //*******************初始化*******************
    int i = 0, j = 0, k = start;
    int leftSize = mid - start + 1;
    int rightSize = end - mid;
    int left[leftSize];
    int right[rightSize];
    for (i = 0; i < leftSize; i++)
    {
        left[i] = arr[start + i];
    }
    for (i = 0; i < rightSize; i++)
    {
        right[i] = arr[mid + 1 + i];
    }
    i = 0;
    //*******************选择更小的插入原数组*******************
    while (i < leftSize && j < rightSize)
    {
        if (left[i] <= right[j])
        {
            arr[k++] = left[i++];
        }
        else
        {
            arr[k++] = right[j++];
        }
    }
    //*******************处理越界*******************
    while (i < leftSize)
    {
        arr[k++] = left[i++];
    }

    while (j < rightSize)
    {
        arr[k++] = right[j++];
    }
}

void mergeSort(int arr[], int start, int end)
{
    if (start < end)
    {
        int mid = start + (end - start) / 2;

        mergeSort(arr, start, mid);   // 左递归
        mergeSort(arr, mid + 1, end); // 右递归
        merge(arr, start, mid, end);  // 合并
    }
}